package com.zyk.leetcode;

import java.util.HashMap;
import java.util.Map;

/**
 * @author zhangsan
 * @date 2021/5/3 11:01
 */
public class C930 {

    // 暴力解, 每个开头都是
    public static int numSubarraysWithSum(int[] A, int S) {
        int cnt = 0, n = A.length;
        for (int i = 0; i < n; i++) {
            int sum = 0;
            for (int j = i; j < n; j++) {
                sum += A[j];
                if (sum == S) {
                    cnt++;
                } else if (sum > S) {
                    break;
                }
            }
        }
        return cnt;
    }

    public static int numSubarraysWithSum2(int[] arr, int K) {
        int N = arr.length;
        int[] P = new int[N + 1];
        for (int i = 0; i < N; ++i)
            P[i + 1] = P[i] + arr[i];

        Map<Integer, Integer> count = new HashMap<>();
        int ans = 0;
        for (int x : P) {
            ans += count.getOrDefault(x, 0);
            count.put(x + K, count.getOrDefault(x + K, 0) + 1);
        }
        return ans;
    }


    // for test
    public static void main(String[] args) {
        int[] A = {0, 0, 0, 0, 0};
        int S = 0;
        System.out.println(numSubarraysWithSum(A, S));
    }

}
